The 640 MEG Shareware Studio 2/The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO/clang/jcool01.zip/TODO

Text File | 1992-11-30 | 17KB | 475 lines

--- ToDo list Dec 1992 by Jamshid Afshar ([e-mail]) ---

o ascii_duration() is stupid about years  1 Jan 1992 - 31 Dec 1991 is
*not* "1 year 1 day".

o Fix bugs in random, quaternion, and complex -- code probably
assumes 32-bit ints.  Their test_*.C programs have bugs which crash
the machine, so I commented them out of the tests\makefile.

o Turn inlining back on (-vi) once I get a BC++ that inlines without
causing weird run-time bugs.

o Get rid of Envelope class.  Besides probably not being strictly
valid C++ because it relies on temporaries hanging around, I think
compiler optimizations could reap a lot of its benefits.  Also, maybe
same optimization could be done less obscurely by using Shared data
members instead.

o Why is NT_Stack_Entry first_element a long instead of a pointer?!

o Change Range<Bounds> back to Range<T, T max, T min> since this is
legal after all (a BC++ 3.1 bug didn't allow original code). (that's
why ex3_12 is commented out in examples/makefile).

o Remove all use of <values.h> -- use INT_MIN,etc. instead of MAXINT,etc.
(mostly just in Complex and Rational)

o Change all #include <misc.h> to #include <cool/misc.h> so don't have
to have cool and cool/.. in path.  Maybe rename (or remove) Boolean.

o Get rid of (int n, Type t, ...) ctors in List, Vector, etc. since
they cause overloading ambiguities and they're rarely useful (only
built-in types).

o Get rid of all the "== TRUE" tests in (*compare)() calls.  Add
template parameter Comparator instead of using compare functions

o For all array indexes change ulong->size_t, long->size_t but check
arithmetic since sometimes relies on negative values.

o Redo error handling; code relies on coolcpp's ability to to
stringize template parameter name; do something upwardly compatible
with throw (maybe something like Johan Bengston's paper).

o Use CoolList_H instead of LISTH as macro wrapper so as not to
conflict with other List.h headers.  Also get rid of #ifndef around
each #include statement -- let the compiler do this optimization.

o Possibly #include <cool/*.C> in each header file unless next version
of compilers implement automatic instantiation of template functions.

o Maybe change to more modern, POSIX Regexp?



---- The following is the todo list that was in the GECOOL2.1 package ----

File: List.h

  Create nodes with a reference count of 1, then eliminate all the
  reference method calls on new nodes. (new nodes are ALWAYS referenced
  by something...)
done - LGO 10/2/89

1. Fix bug in division and modulo of 2 bignums.
    Reason: Overflow is not always catched with fixnum multiplication.
    Fix in estimate_q_hat.
DONEFile: Date_Time.C

localtime(long) has 1 array bound write error and "delete (tm*) t" causes
warings from Purify: freeing t which is not the begining of a malloc bloc.
IGNORE

Fix memory leak caused by tzset() called in set_tz(time_zone).
This call is done by localtime already, and only once.
DONE


Vector.h
 Bug in ... in constructor, using va_arg.
 The arguments in ... cannot be passed by reference. macro va_arg does funny
 casting and does not enforce argument passing correctly, especially in case
 of passing by reference.

prepend, remove_duplicates
 Don't call constructors or operator= on the elements of this->data


 operator[], fill, copy
 When checking array boundaries, instead of
   if (n < 0 || n >= this->number_elements)    // If index out of range
 do:
   if ((unsigned long) n >= this->number_elements)
 The cast makes negative n look very large.
DONE

 operator==, position, search, push_new, remove, remove_duplicates, replace,
 replace_all
 This sits in a loop calling (*this->compare).  Instead, make this->compare
 default to NULL, and have two loops: one for the default case where
 operator== on the value type is used, and another calling (*this->compare).
operator== and search are special cases
DONE

 search, push_new, remove, remove_duplicates, replace, replace_all
 there ought to be a general purpose, protected searching method, which is
 fast (see above) used by all these methods.
Used find - DONE

 copy, push, push_new, append, prepend, insert_before, insert_after
 There needs to be a general purpose protected grow method, like in String.
 The grow method should call resize to do most of the work.
DONE

 reverse
 This could be re-written to use pointers instead of indices.
 Dividing the length by two can be eliminated, and a check for when
 the top and bottom pointers meet or cross substituted.

 remove, remove_duplicates, prepend, insert_before, insert_after
 These need to be re-written to do their work in-place (i.e. no copying
 to a temporary)  The new and delete calls should go away.
DONE - prepend left as-is because it's likely to grow the vector

 insert_before, insert_after
 There are two versions of each of these.  They should all call a common
 private method which does the real work of inserting something at some index.
DONE

 type##_vector_heap_sort
 This needs to be merged into the sort method.  There's no reason for
 this friend function to exist, and it causes an extra .o file to be
 produced by the implement script.
DONE

 sort
 Use the ansi C qsort function, instead of having one in the template.
 If you feel that the heap sort algorithm is superior, write a general
 purpose hsort function, with the same calling sequence as qsort.
 hsort can be in the library instead of the template.
DONE

 Vector<Type>(int n, Type* data)
 Write a new constructor which makes a fixed size vector which shares
 storage with the data argument
DONE

Matrix.h
 Bug in ... in constructor, using va_arg.
 The arguments in ... cannot be passed by reference. macro va_arg does funny
 casting and does not enforce argument passing correctly, especially in case
 of passing by reference.

  In all the constructors:
  Allocate all the column data in one chunk, then fill in the
  addresses in the row vector.
DONE

  ~Matrix, operator=,
  When deleting the matrix, delete only the first row, then the column
  (see above)
DONE

  operator+ operator* etc. (All non-destructive operators)
  DON'T RETURN A REFERENCE TO STORAGE ON THE HEAP.  Return a Matrix on
  the stack by value.  Use the copy constructor, then the associated
  operator?= function.
DONE

  operator*=
  This allocates row vectors on the heap, then doesn't delete them!
  Anyway, this needs to be re-written to use a single temporary row
  vector, instead of a whole new matrix.

  inline Type& operator[](int row, int col)
  New method, does the same thing as the current get method.
DONE

  inline const Type& get (int, int);
  change this to return Type, instead of a const reference to type.
  (We're always dealing with numbers, right? so there's no need to
  deal in references to Type.)
DONE

  Nuke the map and reduce methods
DONE

File: Stack.h

Fix memory leak, in &=, |=, ^=, -=.
The leak comes from returning by value, a stack allocated on the heap.
The stack is copied and returned, and the one on the heap is never deleted.
DONE

Add a general purpose protected grow method
DONE

  push pushn
  use the grow method.
DONE

 operator==, find, position
 These sit in a loop calling (*this->compare).  Instead, make this->compare
 default to NULL, and have two loops: one for the default case where
 operator== on the value type is used, and another calling (*this->compare).
DONE

 Stack<Type>(int n, Type* data)
 Write a new constructor which makes a fixed size Stack which shares
 storage with the data argument.
DONE
Queue.h

  unget, put
  Call a general purpose grow method, which calls resize to do most of
  the work.
DONE

  remove
  Rewrite to remove in-place, instead of copying the whole queue.
DONE

  set_length
  Currently, if the length specified is greater than the size, the
  length is set to the size.  This is wrong.  It should resize the
  queue to be large enough for length.

  The whole implementation is inefficient.  number_elements should NOT
  be maintained, but calculated.  Things like get and put should be
  trivial inlines, not 20 line functions.
DONE

  I think the names first_in and last_in are confusing.  I would call
  them in and out.
DONE

  In addition, since queue always works sequentially,
  it's better to use pointers instead of array references [].


  There needs to be additional overloaded versions of get and unput, which
  take a reference to a return value, and return a Boolean success flag.
DONE
file: Association.h

find
  re-write this to not use reset next and key.  find is heavily used,
  and setting current position inside the loop (instead of using a local
  variable in a register) slows it down
template <class Ktype, class Vtype>
Boolean Association<Ktype,Vtype>::find (const Ktype& key) {
  for (long i = 0; i < this->number_elements; i++) // Search for key in list
   if ((*this->compare_keys_s)(this->data[i].get_first(), key) == TRUE) {
     this->current_position = i;    // Set current position
     return TRUE;            // Return success
    }
  return FALSE;                // Return failure
}

remove()
  re-write to invoke the base class remove() method.

remove (const Ktype& key)
  re-write to do a find(key) followed by remove()

put
  put needs to call the general purpose protected grow method, that
  Vector should have (see cool/Vector/TODO)


Make the (base) ~Hash_Table() destructor method inline.

Get rid of the Hash_Table<Tkey,Tval>::Hash_Table<Tkey,Tval> () constructor
and give the constructor that takes a size a default argument:
Hash_Table<Tkey,Tval>::Hash_Table<Tkey,Tval> (int n=1) : (n) {
Do the same for the base Hash_Table class.

Move the "traversed" flag in the current position out of Hash_Table, and
only support it in the Set class.

Use the following for setting current position:
#define make_current_position(hash, index) ((hash << 8) | index)
this->current_position.data = make_current_position(hash, index);
This helps out compilers that don't optimize well (-g option)
and will be faster, if the "traversed" flag is left in.

The resize method can be improved by using the overloaded operator new
in cfront 2.0 to only construct the new buckets, avoid calling the
destructor for the old buckets, and avoid operator= by using memcpy (see
Vector<Type>::resize)

Don't try saving the current position in the remove method.  Since it
doesn't always work, it should never be done.

Re-write Boolean Hash_Table<Tkey,Tval>::remove (const Tkey& key);
to do a find(key) followed by remove();
(this reduces the amount of code generated for each hash table)

Operator= shouldn't make the sizes of the two hash tables the same,
it should just copy the contents.  The current algorithm should be
an optimization for the case where the two sizes are already equal,
or less than.

Operator== shouldn't depend on the two hash table's having the same
number of buckets.  It should first check for the number of entries
being the same (which it does), then for each element in the first hash
table, do a find on the second, and compare the values.  The current
algorithm should be used as an optimization for the case where the two
hash tables have the same number of buckets.
DONE

find, put, get and remove all have the following inner-loop code:
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  int index = this->items_in_buckets[hash];
  for (int i = 0; i < index; i++)        // For each item
    if ((*this->compare_keys)(key,this->table[hash].data[i].key) == TRUE)
      //DO SOMETHING

Get rid of the function call in the inner loop by making compare_keys
default to NULL, and moving the default code to a general purpose find
method.  Do the same for default_hash.
The above code can be replaced with:

  unsigned long hash;
  int i = this->internal_find(key, &hash);
  if (i < 0) DO_SOMETHING
  else DO_SOMETHING_ELSE

// Returns bucket index, or -1 if not found
// If hash_return is non-null, return the hash value
// If hash_return is null, this function returns the hash value
// (this feature is used by the resize method)

long Hash_Table<Tkey, Tval>::internal_find(Tkey key, long* hash_return) {
  long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  long hash;
  //
  // Get the hash value
  //
  if (this->h_function != NULL)
    hash = ((*this->h_function)(key)) % prime;
  else {
#if ISSAME(Tkey, charP) || ISSAME(Tkey, String)
    hash = sxhash(key) % prime;
#else
    if (sizeof (key) <= 4)
      hash = (((unsigned long) key) >> 3) % prime;
    else
      hash = sxhash((char*) &key) % prime;
#endif
  }
  if (hash_return == NULL)
    return hash;
  else
    hash_return = hash;
  //
  // Find the bucket entry
  //
  int index = this->items_in_buckets[hash];
  Tkey##_##Tval##_hash_pair bucket[BUCKET_SIZE] = this->table[hash].data;
  if (this->compare_keys == NULL) {    // DEFAULT COMPARE FUNCTION
#if ISSAME(T1, charP)
 #ifndef C_STRINGH
   extern int strcmp (const char*, const char*);
 #endif
    for (int i = 0; i < index; i++)        // For each item
      if (!strcmp(key,bucket[i].key))
        return i;
#else
    for (int i = 0; i < index; i++)        // For each item
      if (key == bucket[i].key)
        return i;
#endif

  } else {                // VARIABLE COMPARE FUNCTION
    for (int i = 0; i < index; i++)        // For each item
      if ((*this->compare_keys)(key, bucket[i].key))
        return i;
  }
  return -1;
}

This method replaces default_hash and Default_Hash_Compare.  In
addition, it eliminates several function calls in all the lookup
methods, and reduces code duplication (i.e. reduces the amount of code
generated for each hash table)
File: Set.h

Enforce const for set operations + - ^ |, etc...
Currently, const cannot be enforced because the curpos pointer changes.
Save curpos and restore it, so that const is enforced.
DONE

********
*** All the comments in cool/Hash_Table/TODO apply to Set
********

operator| operator^
  These can be re-written to copy "this" to a temporary, and call
  the matching operator|= or operator^= method.
  For example:

template <class Type>
Set<Type> Set<Type>::operator| (Set<Type>& s) {
  Set<Type> result(this->length() + s.length()); // Temporary variable
  for (this->reset(); this->next (); )        // For each entry in 1st set
    result->put (this->value());        // Put entry to result set
  result.operator|=(s);
  return result;                // Return resulting union
}

test_Set depends on the hash sequence of the Sun/4.  This needs to be fixed.
1. Check AVL tree for balancing after put and remove. ex9_7.C
   the tree can be balanced further...

All files:

Split the template files into header (.h) and source (.C).
Eliminate Coolcpp syntax, and make all templates conformant to AT&T C++ 3.0,
and GNU g++ 2.0.

Efficient initialization in constructors by passing initial values to slots
directly, rather that making assignments in body of constructors.

Implement association and other classes based on stack rather than vector,
since LIFO is usally a better than FIFO. Currently there is a lot of shuffling
and copying inside of vector, each time an element is inserted or deleted.


Make sure that operator= works if left hand side is the same object as right
hand side of =.
DONE

A lot of COOL objects copy by ints, and so create array bounds, read writes
on free memory, when the sizeof(object) is not an integral multiplier of
sizeof(int).
Use Purify to check for access errors.
DONE

Fix memory leaks, using infinite loop and watching memory usage with top4.1.
Use Purify to check for leaks.
DONE



All files:

Either implement sharing of nodes in the trees, or do explicit copy.
Currently the trees share the nodes without any reference count.
Choose to do explicit deep copy for now.
DONE

Fix memory leak for Binary_Tree and N_Tree.
Make destructor virtual where necessary.
DONE

File AVL_Tree.h:

Fix balancing bug in AVL tree.
see ../examples/section9/ex9_7.C for bug occurence.
./list/todo
./bignum/todo
./date_tim/todo
./vector/todo
./matrix/todo
./stack/todo
./queue/todo
./associat/todo
./hash_tab/todo
./set/todo
./examples/section9/todo
./todo
./tree/todo